package com.lsa.cormen.ch15.samples;

import java.io.File;
import java.util.ArrayList;
import java.util.List;

import org.apache.commons.io.FileUtils;

public class TextAlignment {
    /**
     * @param args
     * @throws Exception 
     */
    public static void main(String[] args) throws Exception {
        String text = FileUtils.readFileToString(new File("data/samples/cormen/ch15/alignmentInput2.txt"));
        String[] words = text.split("\\b");
        List<String> wordsFiltered = new ArrayList<String>();
        for (String w : words) {
            w = w.trim();
            if (!w.isEmpty() /*&& !w.matches("[.,!'?]+")*/) {
                wordsFiltered.add(w);
            }
        }
        
        final int width = 80; // width of the page
        Integer[] splits = splitDp(wordsFiltered, width);
//        Integer[] splits = splitGreedy(wordsFiltered, width);
        
//        splits = Arrays.asList(splits).subList(0, splits.length / 2).toArray(new Integer[0]);
        printSplitWords(wordsFiltered, splits);
        
        printHeader(width);
        printSplitted(width, wordsFiltered, splits);
    }
    
    private static Integer[] splitDp(List<String> words, int width) {
        final int n = words.size();
        State[] dp = new State[n + 1];
        dp[n] = new State(0, -1);
        
        for (int i = n - 1; i > -1; i--) {
            int min = Integer.MAX_VALUE;
            int minJ = -1;
            for (int j = i + 1; j < n + 1; j++) {
                int newBadness = badness(i, j, words, width) + dp[j].badness;
                if (newBadness < min) {
                    minJ = j;
                    min = newBadness;
                }
            }
            dp[i] = new State(min, minJ);
        }

        List<Integer> splits = new ArrayList<Integer>();
        int i = 0;
        while(dp[i].parent < n) {
            splits.add(dp[i].parent);
            i = dp[i].parent;
        }
        
        return splits.toArray(new Integer[0]);
    }
    
    private static int badness(int i, int j, List<String> words, int width) {
        List<String> subLine = words.subList(i, j);
        int totalW = 0;
        for (String w : subLine) {
            totalW += w.length() + 1;
        }
        
        int badness = Math.abs(width - totalW);
        if (totalW > width) {
            badness = badness * 10;
        }
        
        return badness;
    }

    private static class State {
        int badness;
        int parent;
        
        private State(int badness, int parent) {
            this.badness = badness;
            this.parent = parent;
        }

        @Override
        public String toString() {
            return String.format("State [badness=%s, parent=%s]", badness,
                    parent);
        }
    }

    private static void printSplitted(final int width,
            List<String> wordsFiltered, Integer[] splits) {
        System.out.print("|");
        
        int curSplit = 0;
        int curLen = 0;
        int badnessSum = 0;
        int prevBreak = 0;
        for (int i = 0; i < wordsFiltered.size(); i++) {
            String w = wordsFiltered.get(i);
            if (curSplit < splits.length && splits[curSplit] == i) {
                for (int j = 0; j < width - curLen; j++) {
                    System.out.print(" ");
                }
                badnessSum += badness(prevBreak, i, wordsFiltered, width);
                prevBreak = i; // i == splits[curSplit]
                System.out.println("|");
                System.out.print("|");
                curSplit++;
                curLen = w.length() + 1;
            }
            else {
                curLen += w.length() + 1;
            }
            System.out.print(w+(curLen <= width || curSplit >= splits.length? " " : ""));
        }
        System.out.println();
        printHeader(width);
        System.out.println(String.format("badness=%s", badnessSum));
    }

    public static void printHeader(final int width) {
        for (int i = 0; i < width+2; i++) {
            System.out.print("#");
        }
        System.out.println("");
    }
    
    private static void printSplitWords(List<String> wordsFiltered,
            Integer[] splits) {
        for (int i = 0; i < splits.length; i++) {
            System.out.print(wordsFiltered.get(splits[i]) + " ");
        }
        System.out.println();
    }

    public static Integer[] splitGreedy(List<String> words, int width) {
        List<Integer> splits = new ArrayList<Integer>();
        int curWidth = 0;
        for (int i = 0; i < words.size(); i++) {
            String w = words.get(i);
            int len = w.length();
            if (curWidth + len + 1 <= width) {
                curWidth += len + 1;
            }
            else { // no way this word can fit
                if (i > 0) {
                    splits.add(i);
                }
                curWidth = len + 1;
            }
        }
        return splits.toArray(new Integer[0]);
    }
}